package com.captain.lc.动态规划;

import java.util.Arrays;

/**
 * Des:
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * <p>
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * @author XL
 * @Date 2021/10/19 13:30
 *///
public class CoinChange322 {

    /**
     * Des:暴力递归,出现
     *
     * @param n 硬币数
     * @return {@link int }
     * @author captain
     * @date 2021/10/20 14:36
     */
    public int coins(int n) {
        //解题思路: coins n 代表 n面值时所需要的最小硬币数
        //退出循环条件
        if (n < 1) return Integer.MAX_VALUE;
        if (n == 1 || n == 5 || n == 20 || n == 25) return 1;
        //确定核心逻辑
        //每一个面值都有4种选择
        int min1 = Math.min(coins(n - 25), coins(n - 20));
        int min2 = Math.min(coins(n - 5), coins(n - 1));
        //最后结果
        return Math.min(min1, min2) + 1;
    }

    /**
     * des:
     * 记忆化搜索
     *
     * @param n 面值
     * @return {@link int }
     * @author captain
     * @date 2021/10/21 16:12
     */
    public int coin1(int n) {
        //解题思路: dp[n] 代表凑够n分需要的最少硬币个数
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        //初始化值
        int[] faces = new int[]{1, 5, 20, 25};
        for (int face : faces) {
            //如果n 小于了face , 那么dp[face] 就出现越界问题 dp的length = 20 dp[25] 就越界了
            if (n < face) {
                continue;
            }
            dp[face] = 1;
        }
        return coin1(n, dp);
    }

    public int coin1(int n, int[] dp) {
        //跳出循环
        if (n < 1) return Integer.MAX_VALUE;
        if (dp[n] == 0) {
            //核心逻辑 , 求解dp[n] 需要的最少硬币数
            int min1 = Math.min(coin1(n - 25, dp), coin1(n - 20, dp));
            int min2 = Math.min(coin1(n - 5, dp), coin1(n - 1, dp));
            dp[n] = Math.min(min1, min2) + 1;
        }
        return dp[n];

    }

    /**
     * des:
     * 递推的方式 , 非递归的方式来求解, 动态规划 , 由小变大
     *
     * @param n 面值
     * @return {@link int }
     * @author captain
     * @date 2021/10/21 16:38
     */
    public int coin2(int n, int[] faces) {
        //解题思路: dp[n] 代表凑够n分需要的最少硬币个数
        if (n == 0) return 0;
        if (n < -1) return -1;
        int[] dp = new int[n + 1];
        Arrays.sort(faces);
        //初始化
        //从1 开始 到 n结束
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            //dp[i] 时 , 代表凑够n分需要的最少硬币个数
            for (int face : faces) {
                //剪枝
                if (i < face) continue;
                min = Math.min(dp[i - face], min);
            }
            if (min == Integer.MAX_VALUE) return -1;
            dp[i] = min + 1;
        }
        return dp[n];
    }

    /**
     * des:
     * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
     * <p>
     * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
     *
     * @param coins  货币数
     * @param amount 货币金额
     * @return {@link int }
     * @author captain
     * @date 2021/10/21 17:31
     */
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0 || coins == null || coins.length == 0) return -1;
        //dp[i] 总金额为i 时,需要的最少的硬币个数为 dp[i]
        int[] dp = new int[amount + 1];
        //account = 1 从1 往上推导
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            //当为 i 金额时 , 可能出现的情况为 i - coins的每一个数
            for (int coin : coins) {
                //如果当前总金额小于硬币数, 则直接跳过 , 例如金额 = 3  硬币为5 , 肯定是不符合条件的;
                if (i < coin) continue;
                min = Math.min(min, dp[i - coin]);
            }
            //找到i 总金额的最小值 如果说一直不符合条件的情况, min 还是 min = Integer.MAX_VALUE;
            if (min == Integer.MAX_VALUE) {
                dp[i] = Integer.MAX_VALUE;
            } else {
                dp[i] = min + 1;
            }
        }
        //得出所有的结果
        //如果没有找到 , dp[account] = Integer.MAX_VALUE
        if (dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[amount];

    }

    public static void main(String[] args) {
        System.out.println(new CoinChange322().coinChange(new int[]{2}, 4));
    }
}
